1. Field of the Invention
The present invention relates generally to an apparatus and method for channel coding in a communication system, and more particularly, to an apparatus and method for coding input bits using a fountain code as a channel coding technique.
2. Description of the Related Art
A fundamental purpose of a communication system is to deliver information over a communication channel without errors. When a communication channel has error-free fidelity, a recipient may receive the same data as the data transmitted by a sender, over the communication channel.
However, distortion of information due to noise, fading, and Inter-Symbol Interference (ISI) may occur in communication channels considered in the practical application, creating a need for techniques for overcoming this problem.
Recently, many studies have been conducted on error-correcting codes to increase reliability of communication by efficiently restoring the distortion of information.
In order to maximize data throughput, use of an error-correcting code is required, which is designed to have the optimal performance depending on the reliability of the communication channel and the characteristic of information to be transmitted. For example, a communication channel that usually has high fidelity but also has low reliability for a specific time period, needs to use an error-correcting code which is robust against burst errors.
For example, in an Internet-based protocol such as Transmission Control Protocol/Internet Protocol (TCP/IP), an Automatic Repeat reQuest (ARQ) technique is used as a method for overcoming the effects of packet loss.
In the ARQ technique, a receiver transmits an ACKnowledgement (ACK) signal to a transmitter upon normally receiving a packet, but transmits a Negative ACK (NACK) signal to the transmitter upon detecting an error in a packet. After transmitting a packet to the receiver, the transmitter retransmits the packet both when it has received a NACK signal for the packet from the receiver, and when it has failed to receive an ACK signal for the packet from the receiver.
The ARQ technique ensures efficient delivery of information in one-to-one communication between a transmitter and a receiver when there is a high-fidelity feedback channel over which the receiver may deliver information to the transmitter. However, efficiency of the ARQ technique is drastically reduced when one transmitter delivers information to a plurality of receivers or when a plurality of transmitters deliver information to a plurality of receivers. In addition, it is difficult for the ARQ technique to be applied when fidelity of a feedback channel is low or when the feedback channel is unavailable.
To solve these problems of the ARQ technique in a multi-to-multi communication system, erasure codes such as a fountain code have been disclosed.
The fountain code may also be called a rateless code because the amount of coded data is not predetermined when a coding rate of channel coding is expressed as the amount of original information divided by the amount of coded data. The fountain code may enable complete reception without error merely with unidirectional transmission even when bidirectional transmission of information is difficult, such as when a transmitter does not have sufficient information about a receiver(s) and when there are a large number of receivers.
A Raptor code, which is a type of fountain code, was developed by Amin Shokrollahi in 2004. The Raptor code has been adopted as the standard technology in the application layer of Digital Video Broadcasting-Handheld (DVB-H). The Raptor code has better performance than a Luby-Transform (LT) code, the existing fountain code, in terms of computation in a decoding process. The biggest drawback of the LT code is that the computation required to restore information bits from coded bits is nonlinear, whereas the Raptor code enables its decoding while maintaining coding computation within the linear range, thereby solving the shortcomings of the LT code.
Generally, a systematic code including information bits among bits (i.e., coded bits) of a codeword to be transmitted, exhibits excellent performance compared to a non-systematic code including no information bits among the bits of the codeword. However, the Raptor code disclosed to this date requires coding complexity of O(k2) for k information bits, in making a systematic code. Due to the high coding complexity, a Raptor code having the form of a systematic code cannot be practically realized. Therefore, there is a need in the art for a systematic Raptor code having low coding complexity.
Additionally, an optimal coding method for the fountain code is needed in the art, because the number of received bits used for decoding is different according to the channel state.